{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Greatness of an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximizeGreatness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大化数组的伟大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 0 开始的整数数组&nbsp;<code>nums</code>&nbsp;。你需要将&nbsp;<code>nums</code>&nbsp;重新排列成一个新的数组&nbsp;<code>perm</code>&nbsp;。</p>\n",
    "\n",
    "<p>定义 <code>nums</code>&nbsp;的 <strong>伟大值</strong>&nbsp;为满足&nbsp;<code>0 &lt;= i &lt; nums.length</code>&nbsp;且&nbsp;<code>perm[i] &gt; nums[i]</code>&nbsp;的下标数目。</p>\n",
    "\n",
    "<p>请你返回重新排列 <code>nums</code>&nbsp;后的 <strong>最大</strong>&nbsp;伟大值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,3,5,2,1,3,1]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>一个最优安排方案为 perm = [2,5,1,3,3,1,1] 。\n",
    "在下标为 0, 1, 3 和 4 处，都有 perm[i] &gt; nums[i] 。因此我们返回 4 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,3,4]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>最优排列为 [2,3,4,1] 。\n",
    "在下标为 0, 1 和 2 处，都有 perm[i] &gt; nums[i] 。因此我们返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-greatness-of-an-array](https://leetcode.cn/problems/maximize-greatness-of-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-greatness-of-an-array](https://leetcode.cn/problems/maximize-greatness-of-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,2,1,3,1]', '[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        nums2 = nums.copy()\n",
    "        for i, n in enumerate(nums2[::-1], 0):\n",
    "            while nums and nums[-1] <= n:\n",
    "                nums.pop()\n",
    "            if not nums:\n",
    "                break\n",
    "            nums.pop()\n",
    "\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        idx = 0\n",
    "        for num in nums:\n",
    "            if num > nums[idx]:\n",
    "                idx += 1\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        #[1,2,2,3]\n",
    "        #[2,3]\n",
    "        nums.sort()\n",
    "        r=1\n",
    "        ans=0\n",
    "        l=0\n",
    "        while r<len(nums):\n",
    "            while r<len(nums) and nums[r]<=nums[l]:\n",
    "                r+=1\n",
    "            \n",
    "            if r<len(nums):\n",
    "                ans+=1\n",
    "            #print(l,r)\n",
    "            l+=1\n",
    "            r+=1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        for x in nums:\n",
    "            if x >nums[i]:\n",
    "                i+=1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nl=len(nums)\n",
    "        ans=0\n",
    "        nums.sort()\n",
    "        i=nl-1\n",
    "        j=i-1\n",
    "        while j>=0 and i>=1:\n",
    "            if nums[i]>nums[j]:\n",
    "                ans+=1\n",
    "                i-=1\n",
    "                j-=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return ans       \n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums:\n",
    "            if x > nums[i]:\n",
    "                i += 1\n",
    "        return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(nums) and j < len(nums):\n",
    "            if nums[i] < nums[j]:\n",
    "                res += 1\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums1 = sorted(nums)\n",
    "        nums2 = deque(nums1)\n",
    "        ans = 0\n",
    "        for i in range(len(nums1)):\n",
    "            while nums2 and nums2[0] <= nums1[i]:\n",
    "                nums2.popleft()\n",
    "            if not nums2:\n",
    "                break\n",
    "            nums2.popleft()\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        s = sorted(nums)\n",
    "        ans = 0 \n",
    "        i = 0\n",
    "        j = 1\n",
    "        while i < len(s) and j < len(s):\n",
    "            if s[i] < s[j]:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = [0] * n\n",
    "        las,tt = -1,0\n",
    "        for i,v in enumerate(nums):\n",
    "            if v == las:\n",
    "                m[i] = tt\n",
    "                tt += 1\n",
    "            else :\n",
    "                m[i] = 0\n",
    "                las = v\n",
    "                tt = 1\n",
    "        \n",
    "        c = [0] * (n+10)\n",
    "        for i in range(n):\n",
    "            s,e = m[i]+1,i\n",
    "            c[s] += 1\n",
    "            c[e+1] += (-1)\n",
    "        pp = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pp += c[i]\n",
    "            ans = max(ans,pp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        reverse_nums = sorted(nums, reverse=True)\n",
    "        reverse_nums_copy = copy.deepcopy(reverse_nums)\n",
    "        ans = 0\n",
    "        while reverse_nums and reverse_nums_copy:\n",
    "            while reverse_nums_copy and reverse_nums_copy[-1] <= reverse_nums[-1]:\n",
    "                reverse_nums_copy.pop()\n",
    "            if reverse_nums and reverse_nums_copy:\n",
    "                reverse_nums.pop()\n",
    "                reverse_nums_copy.pop()\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        arr = nums.copy()\n",
    "        arr.sort()\n",
    "        nums.sort()\n",
    "        i = 0 \n",
    "        j = 0\n",
    "        length = len(nums)\n",
    "        ans = 0\n",
    "        while(i<length and j<length):\n",
    "            if nums[i]<arr[j]:\n",
    "                ans+=1\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums:\n",
    "            if x > nums[i]:\n",
    "                i += 1\n",
    "        return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        nums.sort()\n",
    "        for x in nums:\n",
    "            if x > nums[i]:\n",
    "                i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        # 1 1 1 2 3 3 5\n",
    "\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while j < n:\n",
    "\n",
    "            while j < n and nums[i] == nums[j]: j+=1\n",
    "\n",
    "            if j < n and nums[i] < nums[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                res += 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        for x in nums:\n",
    "            if x > nums[i]:\n",
    "                i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        p=0\n",
    "        q=1\n",
    "        ans=0\n",
    "        while q<len(nums):\n",
    "            if nums[q]>nums[p]:\n",
    "                ans+=1\n",
    "                p+=1\n",
    "            q+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximizeGreatness(self, A: List[int], left=0) -> int:\n",
    "\n",
    "        return reduce(lambda left, x: left + (A[left] < x), A := sorted(A), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        i, j = 0, 0\n",
    "        while j < len(nums):\n",
    "            if nums[j] > nums[i]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        i = 0\n",
    "        for num in nums:\n",
    "            print(num, nums[i], i)\n",
    "            if num > nums[i]:\n",
    "                i += 1\n",
    "        \n",
    "        return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        perm = sorted(nums)\n",
    "        i = 0\n",
    "        n = len(perm)\n",
    "        ans = 0\n",
    "        #print(f'{perm}')\n",
    "        for x in perm:\n",
    "            #print(f'x={x},i={i}')\n",
    "            while i < n and perm[i] <= x:\n",
    "                i += 1\n",
    "            if i == n: return ans\n",
    "            if perm[i] > x:\n",
    "                i += 1\n",
    "                ans += 1   \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums2 = nums.copy()\n",
    "        nums2 = SortedList(nums2)\n",
    "        res = 0\n",
    "\n",
    "        for num in nums:\n",
    "            n = len(nums2)\n",
    "            i = bisect_right(nums2, num)\n",
    "            if i < n:\n",
    "                res += 1\n",
    "                nums2.remove(nums2[i])\n",
    "            elif i == n and nums2[i-1] > num:\n",
    "                res += 1\n",
    "                nums2.remove(nums2[i-1])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        from heapq import heappush, heappop\n",
    "        q1, q2, res = [], [], 0\n",
    "        for n in nums:\n",
    "            heappush(q1, n)\n",
    "            heappush(q2, n)\n",
    "\n",
    "        while q2:\n",
    "            if q1[0] < q2[0]:\n",
    "                res += 1\n",
    "                heappop(q1)\n",
    "            heappop(q2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        nums从小到大排序，新建一个ls从大到小排序，从头遍历每个nums的值，从ls中pop，\n",
    "        如果大于则找到一个，继续遍历下一个数，当ls为空时，结束\n",
    "        \"\"\"\n",
    "        ls = sorted(nums,reverse = True)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            while ls:\n",
    "                x = ls.pop()\n",
    "                if x > nums[i]:\n",
    "                    count += 1\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        pq = nums[:]\n",
    "\n",
    "        heapq.heapify(pq)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            while pq and pq[0] <= nums[i]:\n",
    "                heapq.heappop(pq)\n",
    "\n",
    "            if not pq:\n",
    "                break\n",
    "            else:\n",
    "                heapq.heappop(pq)\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l, res = nums[::-1], 0\n",
    "        for i in nums:\n",
    "            while l and l[-1]<=i: l.pop()\n",
    "            if not l: return res\n",
    "            l.pop()\n",
    "            res += 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "\n",
    "        s = sorted(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        j = n - 1\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            \n",
    "            while st and s[st[-1]] <= nums[i]:\n",
    "                st.pop()\n",
    "\n",
    "            while j >= 0 and s[j] > nums[i]:\n",
    "                st.append(j)\n",
    "                j -= 1\n",
    "            if st:\n",
    "                st.pop()\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "\n",
    "        s = sorted(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        j = n - 1\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            \n",
    "            while st and s[st[-1]] <= nums[i]:\n",
    "                st.pop()\n",
    "\n",
    "            while j >= 0 and s[j] > nums[i]:\n",
    "                st.append(j)\n",
    "                j -= 1\n",
    "            if st:\n",
    "                st.pop()\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        lst = SortedList(nums)\n",
    "        for x in nums:\n",
    "            i = bisect.bisect_right(lst, x)\n",
    "            if i<len(lst):\n",
    "                ans += 1\n",
    "                lst.pop(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums2 = nums.copy()\n",
    "\n",
    "        n = len(nums)\n",
    "        \n",
    "        idx1, idx2 = list(range(n)), list(range(n))\n",
    "        \n",
    "        idx1.sort(key=lambda x: nums[x])\n",
    "        idx2.sort(key=lambda x: nums2[x])\n",
    "        \n",
    "        res = 0\n",
    "        left, right = 0, n - 1\n",
    "        for i in range(n):\n",
    "            if nums[idx1[i]] > nums2[idx2[left]]:\n",
    "                left += 1\n",
    "                res += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        set_nums = list(set(nums))\n",
    "        if len(set_nums) == len(nums):\n",
    "            return len(nums)-1\n",
    "        ans = 0\n",
    "        size = nums.count(set_nums[-1])\n",
    "        for i in range(len(set_nums)-2,-1,-1):\n",
    "            \n",
    "            nums_i_num = nums.count(set_nums[i])\n",
    "            # print(\"i:\",set_nums[i],\" nums_i_num\",nums_i_num,\" ans:\",ans)\n",
    "            if nums_i_num  <= size:\n",
    "                ans += nums_i_num\n",
    "                size -= nums_i_num\n",
    "            else:\n",
    "                ans += size\n",
    "                size = 0\n",
    "            size += nums_i_num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        return len(nums) - max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        # O(n)\n",
    "        return len(nums) - max(Counter(x for x in nums).values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        from collections import Counter\n",
    "\n",
    "        num_cnt = Counter()\n",
    "        for num in nums:\n",
    "            num_cnt[num] += 1\n",
    "        left = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if left >= len(nums):\n",
    "                break\n",
    "            idx = bisect.bisect_left(nums, nums[i] + 1, left)\n",
    "            if idx == len(nums):\n",
    "                break\n",
    "            left = idx + 1\n",
    "            ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        return len(nums) - max(Counter(nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = len(nums)\n",
    "        key = [(key, cnt[key] - 1) for key in cnt if cnt[key] > 1]\n",
    "        res = 0\n",
    "        for k, n in key:\n",
    "            res = res + n - min(res, n)\n",
    "        return ans - 1 - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        collect = dict()\n",
    "        for i in nums:\n",
    "            if i in collect:\n",
    "                collect[i] += 1\n",
    "            else:\n",
    "                collect[i] = 1\n",
    "        maxlen = 0\n",
    "        for i in collect:\n",
    "            maxlen = max(collect[i], maxlen)\n",
    "        return len(nums) - maxlen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        collect = dict()\n",
    "        for i in nums:\n",
    "            if i in collect:\n",
    "                collect[i] += 1\n",
    "            else:\n",
    "                collect[i] = 1\n",
    "        maxlen = 0\n",
    "        # for i in collect:\n",
    "        #     maxlen = max(collect[i], maxlen)\n",
    "        maxlen = max(collect.values())\n",
    "        return len(nums) - maxlen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        return len(nums) - max(Counter(nums).values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        keys = sorted(cnt.keys())\n",
    "        list1 = [cnt[x] for x in keys]\n",
    "        list2 = list1[:]\n",
    "        L = len(list1)\n",
    "        i, j, ans = 0, 1, 0\n",
    "        while True:\n",
    "            while j < L:\n",
    "                if list1[i] < list2[j]:\n",
    "                    ans += list1[i]\n",
    "                    list2[j] -= list1[i]\n",
    "                    list1[i] = 0\n",
    "                    break\n",
    "                else:\n",
    "                    ans += list2[j]\n",
    "                    list1[i] -= list2[j]\n",
    "                    j += 1\n",
    "            \n",
    "            if list1[i] > 0:\n",
    "                break\n",
    "            \n",
    "            i += 1\n",
    "            j = max(j, i + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        temp = 1\n",
    "        for num in nums:\n",
    "            if num not in dic:\n",
    "                dic[num] = 1\n",
    "            else:\n",
    "                dic[num] += 1\n",
    "                temp = max(temp, dic[num])\n",
    "        return len(nums) - temp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        return len(nums) - max(Counter(nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        bb = Counter(nums)\n",
    "        return len(nums) - bb.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for i in nums:\n",
    "            dic[i] += 1\n",
    "        #nums排序\n",
    "        nums.sort()\n",
    "        #倒序遍历nums\n",
    "        #temp 记录nums最大值\n",
    "        \n",
    "        b = [key for key,val in dic.items()]\n",
    "        b.sort()\n",
    "        res = 0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            temp = b[-1]\n",
    "            if temp == nums[i]:\n",
    "                continue\n",
    "            else:\n",
    "                #正数到0\n",
    "                if dic[temp]>1:\n",
    "                    dic[temp] -= 1\n",
    "                    res+=1\n",
    "                    #没了没了\n",
    "                elif dic[temp] == 1:\n",
    "                    res+=1\n",
    "                    b.pop()\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        ks = SortedList(c.keys())\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            x = ks.bisect_right(nums[i])\n",
    "            if x != len(ks):\n",
    "                ans += 1\n",
    "                c[ks[x]] -= 1\n",
    "                if c[ks[x]] == 0:\n",
    "                    del c[ks[x]]\n",
    "                    ks.remove(ks[x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        return len(nums) - max(Counter(nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeGreatness(self, nums: List[int]) -> int:\n",
    "        return len(nums) - max(Counter(nums).values())\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
